package com.jp.algorithm.segmentTree;

public class SegmentTree {

    int[] array;
    Node root = null;

    public SegmentTree(int[] array){
        this.array=array;
        init(0,array.length-1,null,0);
    }

    class Node{
        public int sum;
        public int start;
        public int end;
        public Node left;
        public Node right;

        public Node(int sum,int start,int end){
            this.sum=sum;
            this.start=start;
            this.end=end;
        }
    }
    //flag 0,root;1,left;2,right
    private void init(int start,int end,Node parent,int flag){
        int sum=0;
        for(int i=start;i<=end;i++){
            sum+=array[i];
        }
        Node node = new Node(sum,start,end);
        if(flag==0){
            root=node;
        }else if(flag==1){
            parent.left=node;
        }else{
            parent.right=node;
        }
        if(start==end)
            return;
        init(start,(end-start)/2+start,node,1);
        init((end-start)/2+start+1,end,node,2);
    }

    public void print(Node node){
        if(node !=null){
            System.out.println(node.sum);
        }else{
            return;
        }
        print(node.left);
        print(node.right);
    }

    public int modify(Node node, int index,int value){
        if((node.start==node.end) && node.start==index){
            node.sum=value;
            return node.sum;
        }
        if(index <=  (node.end-node.start)/2){
            node.sum = modify(node.left,index,value)+node.right.sum;
        }else{
            node.sum = modify(node.right,index,value)+node.left.sum;
        }
        return node.sum;
    }
    public int search(Node node, int start,int end){
        if(node==null)
            return 0;
        System.out.println("start:"+node.start+",end:"+node.end);
        if(start <= node.start && end >= node.end){
            return node.sum;
        }
        return search(node.left,start,end)+search(node.right,start,end);
    }

    public static  void testModify(){
        int[] array= {1,3,5,7,9,11};
        SegmentTree segmentTree = new SegmentTree(array);
        segmentTree.modify(segmentTree.root,2,6);
        segmentTree.print(segmentTree.root);
    }
    public static void testSearch(){
        int[] array= {1,3,5,7,9,11};
        SegmentTree segmentTree = new SegmentTree(array);
        System.out.println(segmentTree.search(segmentTree.root,1,5));
    }

    public static void testInit(){
        int[] array= {1,3,5,7,9,11};
        SegmentTree segmentTree = new SegmentTree(array);
        segmentTree.print(segmentTree.root);
    }
    public static void main(String[] args) {
        //testInit();
        //testModify();
        testSearch();
    }

}
